/*
 * @Author: szx
 * @Date: 2021-10-30 12:53:57
 * @LastEditTime: 2021-10-30 13:06:26
 * @Description:
 * @FilePath: \leetcode\800-899\876\876.cpp
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
#include <iostream>
using namespace std;

// class Solution {
//    public:
//     ListNode* middleNode(ListNode* head) {
//         ListNode* ptr = head;
//         int cnt = 0;
//         while (ptr != nullptr) {
//             cnt++;
//             ptr = ptr->next;
//         }
//         cnt = cnt % 2 == 1 ? cnt / 2 : (cnt + 1) / 2;
//         ptr = head;
//         while (cnt > 0) {
//             ptr = ptr->next;
//             cnt--;
//         }
//         return ptr;
//     }
// };

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};